package easy;

import util.PrintUtils;

import java.util.HashSet;
import java.util.Set;

public class Solution_1089 {

    public void duplicateZeros(int[] arr) {
        Set<Integer> set = new HashSet<>();
        int count = 0;
        for (int i = 0; i + count < arr.length - 1; i++) {
            if (arr[i] == 0) {
                set.add(i);
                count++;
            }
        }
        int endIndex = arr.length - count - 1;
        for (int index = endIndex, i = arr.length - 1; index >= 0; index--) {
            if (arr[index] == 0) {
                arr[i--] = 0;
                if (set.contains(index)) {
                    arr[i--] = 0;
//                    count--;
                }
            } else {
                arr[i--] = arr[index];
            }
        }
        PrintUtils.arrayInt(arr);
    }

    public static void main(String[] args) {
        Solution_1089 model = new Solution_1089();
        model.duplicateZeros(new int[]{9,9,9,4,8,0,0,3,7,2,0,0,0,0,9,1,0,0,1,1,0,5,6,3,1,6,0,0,2,3,4,7,0,3,9,3,6,5,8,9,1,1,3,2,0,0,7,3,3,0,5,7,0,8,1,9,6,3,0,8,8,8,8,0,0,5,0,0,0,3,7,7,7,7,5,1,0,0,8,0,0});
        model.duplicateZeros(new int[]{8,4,5,0,0,0,0,7});
        model.duplicateZeros(new int[]{0, 0, 0, 0, 0, 0, 0});
        model.duplicateZeros(new int[]{1, 0, 2, 3, 0, 4, 5, 0});
        model.duplicateZeros(new int[]{1, 2, 3});
        model.duplicateZeros(new int[]{1, 0, 2, 3, 0, 4, 5, 0});
    }
}
